package ljl.alg.jianzhioffer.round2;

/**
 * 我瞬间想到两个解法，1. 数组作为 map 2. 把数字放到自己位置上，如果位置上的数和自己一样那就是重复了
 * */
public class _03_same_number_in_array {
    
    
    public int findRepeatNumber1(int[] nums) {
        int[] dic = new int[nums.length];
        for (int num : nums) {
            if (++dic[num] > 1)
                return num;
        }
        return -1;
    }
    
    public int findRepeatNumber2(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            while (i != num) {
                if (nums[num] == num)
                    return num;
                nums[i] = nums[num];
                nums[num] = num;
                num = nums[i];
            }
        }
        return -1;
    }
}
